Point-to-point communication across a communication network among a single sender and a single receiver is well known and networking protocols for point-to-point communication services are well established. Increasingly, however, a communications arrangement needs to be established among multiple senders and/or multiple receivers constituting a group having some community of interest. Accordingly, the concept of a group multicast service has evolved for enabling multiple senders to communicate to multiple receivers.
Providing a point to multipoint connection is known in the art. Also several schemes exist for providing a multicast service between multiple senders and multiple receivers. These schemes, however, are not efficient, especially for ATM (Asynchronous Transfer Mode)connection oriented networks. Only a single known methodology efficiently provides a multicast service between multiple senders and multiple receivers: pending application Ser. No. 08/631,869 filed by Ramakrishnan et al. on Apr. 12, 1990 describes and claims a methodology, designated by the acronym SEAM (Scalable Efficient ATM Multicasting).
A brief overview of the SEAM methodology is presented here for convenience of reference. Although the SEAM methodology is described in the context of an ATM network, it should be recognized that the SEAM methodology will be applicable to the provision of multicasting service in other communication networks, particularly other packet and sub-packet networks.
As is well known, networks are a principal means of exchanging or transferring information (e.g., data, voice, text, video, etc.) among communications devices (i.e., devices for inputting and or outputting information such as computer terminals, multimedia workstations, fax machines, printers, servers, telephones, videophones, etc.) connected to the network(s). A network typically comprises switching nodes connected to each other, and to communication devices, by links. Each link is characterized by a link capacity which will generally be specified as a bandwidth or, equivalently, a transmission rate. When information is to be exchanged between two communications nodes/devices, a path is established within the network connecting the nodes (hereafter called the origination and destination nodes) with which those devices are associated. Such a communications path, or channel, between a specified origin and destination may be comprised of a set of physical paths (i.e., serially connected links and their included nodes along with the origin and destination nodes) within the network.
FIG. 1 shows an exemplary wide area network illustrative of the configuration and operation of a contemporary communications network. Network 10 comprises a plurality of switching nodes 20 and links 30. Each of the nodes 20 may also have associated therewith a buffer (not shown) of predetermined size and each of the links 30 will have associated therewith a predetermined traffic handling capacity. Note that the depiction of a network comprising only five nodes is for convenience of illustration, and that an operating network may have a much larger number of nodes and associated connecting links.
Various nodes are shown illustratively connected to Communications Devices 40. It should be understood that the single communications devices shown connected to the nodes in the figure are used for simplicity of illustration, and that an actual implementation of such a network would ordinarily have a number of communications devices connected at each of those nodes. Note, as well, that the illustrated communications devices may also represent another network, such as a LAN, which is connected to network 10.
Each communications device 40 generates information for use by, or receives information from, other communications devices in the network. The term "information" as used herein is intended to include data, text, voice, video, etc. Information from communications device 40 is characterized by a set of transmission and/or rate parameters related to network link and buffer requirements needed to accommodate transmission of such information.
In the design and operation of an information network, such as network 10, a concept that is frequently applied is that of a logical or virtual circuit or virtual connection between sending and receiving communications devices in the network. The basic idea of a virtual connection is that of a logical partitioning of a physical network into a number of virtual circuits generally serving different users and/or services. Such a virtual connection generally follows a single physical path (comprising a series of interconnected links between a sending and a receiving communication device) at any given time. Note, however, that multiple virtual circuits may share capacity in a single physical path through a network.
Communications networks will often use a networking protocol called Asynchronous Transfer Mode (ATM). The development of ATM networks is fueled by the need for efficient utilization of wide-area network resources, scalable bandwidth and support for quality of service. Indeed, it is generally believed that, within the next 5-10 years, most of the voice and data traffic generated throughout the world will be transmitted by ATM technology. Broadband packet networks based on Asynchronous Transfer Mode are enabling the integration of traffic with a wide range of characteristics within a single communication network. In these networks, all communication at the ATM layer is in terms of fixed-size information segments, called "cells" in ATM terminology. An ATM cell consists of 48 bytes of payload and 5 bytes for the ATM-layer header. Routing of cells is accomplished through packet switches over Virtual Connections (hereafter "VC") set up between endpoints. Packets of information may be broken up (or segmented) into multiple cells, each cell carrying the 48 bytes of information sequentially. The destination reassembles the cells received into the original packet. The assumption, at least for cells using the AAL5 (ATM adaption layer, version 5) adaptation layer protocol, is that all of the cells of a packet are delivered in order for a given VC, and hence can be assembled, as they arrive in order.
A defining property of the SEAM methodology is a shared tree between all senders and receivers of a group. The concept of a "core" is used as the root of the tree to be set up. The core acts primarily as an anchor for other nodes to forward signaling messages to it. Thus, every router/switch in the tree participates in the forwarding of traffic, including the router/switch which was chosen to be the core for signaling purposes. The SEAM methodology manages group members who are only senders, only receivers, or both, in the same way. All of these three types of members share one tree, rooted at the core. The tree's links are bi-directional channels. The core may be an ATM switch which provides the added role of being an anchor for signaling messages to be sent toward it, when senders/receivers are added. Segmentation-reassembly is not required at the core and only occurs in the end-systems that are senders and receivers.
Signaling for the multipoint-to-multipoint multicast SEAM methodology is based on a group handle. A handle is a unique conversation identifier for the SEAM methodology. That handle is used in signaling messages to facilitate the association of appropriate input and output ports/VCs for the multicast group in the core and each of the switches/routers in the tree--i.e., the handle for a particular multicast group enables the mapping of input VCs for that group at a particular switch to the corresponding output VC(s) at that switch (in accordance with a routing table set up in each such switch). The handle consists of the core address plus an identifier. The core address is necessary because it allows members and intermediate switches to know the core through the group handle. Note that to make the handle globally unique, it is sufficient to make the additional identifier locally (at the core) unique.
Because a defining property of the SEAM methodology is the use of a shared tree between all senders and receivers, a commonly designated VC (per link) can serve all senders and all receivers in a group. For this shared tree multicasting methodology to work, it is necessary to be able to map multiple incoming VCs into one or several outgoing VCs at switches. While such mapping is straightforward at the packet level, a sub-packet network such as ATM introduces a substantial complication to such a mapping process.
The AAL5 adaptation layer protocol is commonly applied for data transfer applications using ATM. With the AAL5 protocol, a packet is broken up into a number of ATM cells, where those cells are sequentially ordered and related to the underlying packet by the VC identifier and an "end of packet" marker. The cells are then routed through packet switches over VCs set up between endpoints. The destination reassembles the cells received into the original packet. The assumption, at least for cells using the AAL5 adaption layer protocol, is that all of the cells of a packet are delivered in sequential order for a given VC, and hence can be assembled sequentially as they arrive.
In an embodiment of the SEAM methodology, the ATM cells are constructed in accordance with the AAL5 adaptation layer protocol. As explained above, under the shared tree concept of the SEAM methodology, a commonly designated VC serves all senders and all receivers in a group. Thus, multiple links will carry this commonly designated VC, and at least in some instances two or more such links will be connected to input ports of a single switch. Now, since a particular packet is identified by its VC, the occurrence of a common VC at multiple input ports of a switch would result in chaos if the switch mapped from input to output ports in the straightforward manner. That is, if such mapping is done simply on a cell-by-cell basis (by VC identifier and in the order received), then cells belonging to different packets (and contemporaneously arriving at different input ports, but identified by the common VC) will interfere with each other--more particularly, such cells will be interleaved, resulting in corruption of the underlying packets.
With the AAL5 protocol, the constraint imposed by ATM is that the data on a particular VC is ordered. Given that ordering, and the fact that the ATM cell header contains an end-of-packet (EOP) designator, the cells comprising a packet may be determined by the fact that all the cells between two cells with their EOP flag set belonging to the same VC constitute a packet. When a cell containing the EOP flag is received, all the previous cells received on that VC are understood to belong to that packet.
With multiple senders transmitting to the same multicast group, however, these communications arrive on the same commonly-designated VC. Thus, it will be readily appreciated that when multiple senders send packets on the same VC, these packets need to be unambiguously ordered and forwarded so that there is no corruption of the data transmissions. As explained above, such unambiguous ordering and forwarding cannot be accomplished with a straightforward mapping of input VCs to output VCs. With the SEAM methodology, however, such unambiguous ordering and forwarding can be accomplished by having the switches perform a function designated as cut-through. Switches performing this cut-through function forward complete packets at a time, while buffering incoming packets from other input ports until the complete packet has been forwarded, as indicated by the forwarding of an EOP cell for the currently "being forwarded" packet.
To illustrate the operation of this cut-through function, consider the case where two senders, A and B (not shown) are transmitting data packets X and Y respectively to a set of receivers, as depicted in FIG. 2. These data arrive at input ports 1 and 2, respectively, for the indicated switch, which is illustrative of one of the switches in the shared tree. If the networks were packet-based, rather than ATM, where packets were not being segmented into cells, the action of cut-through forwarding is simple: packet X would be transmitted and subsequently packet Y would be transmitted, both being identified by the handle H, which is the group handle. Whichever packet arrived first gets transmitted first.
With ATM networks, however, packets are segmented into cells and senders A and B transmit packets X and Y, with the same VC, which illustratively is designated as VC H. Note that, while it is convenient for illustrative purposes to assume that all VCs are commonly designated by the group handle, "H", in practice each switch port is likely to have a different designation for the group VC, with the association of such different VC designations to the group handle being maintained in routing tables in the switches, based on signaling messages from, or in behalf of, each of the senders and/or receivers in the multicast group. Packets X and Y are distinguished because of the fact that they arrive on different input ports of the switch, even though they arrive on the same logical VC.
Now, as previously noted, because the cell is the unit of transmission, rather than a packet, if the cells from packet X and Y, arriving at input ports 1 and 2, were forwarded without regard to packet association for the cells, it is likely that such forwarded cells will be interleaved resulting in corruption of the underlying packets. Thus it can be seen that forwarding cells in the order received, independent of which port at which they have arrived, on the same outbound VC is undesirable. To overcome this problem, the behavior of packet networks has to be replicated. That is, the cells comprising an entire packet, as received at an input port, are forwarded before any cells received on another input port may be forwarded. In this manner, the receivers do not have to distinguish cells of different packets arriving on the same VC (which would, in any event, be an impossible task).
This cut-through process is carried out by having the following actions carried out at the switch: the first cell of a packet arriving from any input port on VC H determines that this packet arriving on that input port gets unconditional priority to be forwarded on the outgoing VC H. Let this packet be Y from source B. Then, all of the cells of packet Y are forwarded first. Any other packet arriving on any other input port is queued at the switch for forwarding subsequent to the transmission of packet Y. For example, since, under the illustrative hypothesis, the first (and hence all) of the cells of packet X are received after the first cell of packet Y is sent, these are queued. When the last cell of packet Y (signified by the EOP cell, and designated 5Y in the figure) is transmitted, then the cells queued for packet X are transmitted from the switch on the spanning tree. From that point onwards, packet X gets priority for being transmitted on VC H until it has been completely forwarded by the switch. Although the cut-through function described herein has been illustrated in the context of a single switch, it should be understood that this function would be implemented for each switch in the shared tree.
Thus, it will be seen that the requirement on a switch in the shared tree performing "cut-through" is to identify the first cell of an incoming packet on a given multicast VC H, and to transmit cells received on that input port only, until the last cell of that packet has been transmitted. The cells from other input ports that arrive in the meanwhile on VC H are queued for forwarding subsequent to sending the last cell of the currently being forwarded packet.
Furthermore, the switch may be arranged to consider the network transmission speed for packets being received at an input port. For example, it may be known that the transmission speed for packets received at a particular input port will be low--possibly because the port itself is slow, or possibly because the VC on that port has low bandwidth. In that case, forwarding priority may not be granted on the basis of the first input port to receive cells of a new packet. Rather, where such an input port (or the VC on that port) is characterized by a slow transmission speed, cells coming into that port may be buffered and the cells arriving at a higher-speed port forwarded (even though not first in time of arrival at the switch) while the full packet is received for the slower input port. This provides the obvious advantage of avoiding a delay in forwarding packets from higher speed ports due to the switch being tied up waiting for a low speed packet to completely arrive on the low speed port and be processed through the switch.
Another feature of the cut-through methodology relates to a time-out mechanism which can be implemented in the case where the EOP cell of a packet is lost. As discussed above, when a switch has received a packet cell for a given VC, packet cells for that same VC received on other input ports will be buffered until the first received packet is completely received and forwarded. When the packet's EOP marker cell is lost, however, the normal indication that the one of other buffered packets for that same VC can now be forwarded is also lost. To overcome this problem, a time-out can be provided in the cut-through process regarding the waiting time for an additional cell for that on a VC at the input port. Upon timeout, the switch can regenerate a "dummy" EOP cell for the given VC, so that such dummy EOP cell can be forwarded, complete the packet, and thus allow other packets to now be forwarded from other input ports. Such a time-out procedure is only needed when a packet is currently being cut through and the EOP cell has not yet been received at the input port.
The method of performing "cut-through" as described in pending application Ser. No. 08/631,869, however, leaves several issues unresolved. As discussed above, when multicast senders send packets on the same VC, the cells for a given packet need to be completely forwarded in sequential order before cells from other packets with the same VC designation are forwarded; thus, data transmissions are not corrupted due to the interleaving of data which cannot be later de-interleaved. Another problem arises, however, when a packet for one multicast sender is being forwarded on one VC, for example VC1, from a buffer, for example B1, at a switch and packets for VC1 from another multicast sender are buffered, for example B2, at the same switch. While the VC1 packets at B2 remain buffered until VC1 packets at B1 are completely transmitted, additional packets for other VCs, for example VC2, are buffered at B2 behind the VC1 packets. Other VCs such as VC2 can be multicast or unicast VCs. Because the packets for VC1 and the packets for VC2 have different identifiers, no reason exists to postpone the packets for VC2 to be forwarded. In such a case, however, this is not possible because the packet for VC2 is buffered at the end of the B2 queue and cannot be forwarded until the forwarding of packets for VC1 is completed. Where the packets for VC2 are more latency sensitive than the packets for VC1, performance is significantly limited. This is also known as a "head-of-the-line" blocking problem. The potential latency problems can be significantly greater when the above simplified case is expanded to consider a case with several more input ports, multicast VCs and unicast VCs and buffered packets.